import com.sun.source.tree.Tree;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: syyyy
 * Date: 2025-10-10
 * Time: 18:36
 */
public class BinaryTRee {
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val){
            this.val=val;
        }
    }

    //1.二叉搜索树转换为排好序的双向链表
    TreeNode prev=null;
    public void inOrder(TreeNode root){
        if(root==null){
            return;
        }
        inOrder(root.left);
        //当上面这行代码走完要走下一步时，root已经到了二叉树最左边的节点
        root.left=prev;
        if(prev!=null){
            prev.right=root;
        }
        prev=root;//为了第一遍走完之后让prev不等于null
        inOrder(root.right);
    }

    public TreeNode Convert(TreeNode root){
        TreeNode cur=root;
        inOrder(root);
        while(cur.left != null) {
            cur = cur.left;
        }
        return cur;
    }

    public boolean isSymmetrical(TreeNode root){
        if(root == null){
            return true;
        }
        boolean ret=isSymmetricalChild(root.left,root.right);//为什么会想到是两个参数？一个二叉树如果只有根节点那一定是对称二叉树，
        return ret;                                          // 所以我们只需要判读root.left和root.right是否是对称的
    }

    public boolean isSymmetricalChild(TreeNode leftTree,TreeNode rightTree){
        if(leftTree == null && rightTree == null){
            return true;
        }
        if(leftTree != null && rightTree == null || leftTree == null && rightTree != null){
            return false;
        }
        if(leftTree.val != rightTree.val){
            return false;
        }

        boolean ret1=isSymmetricalChild(leftTree.left,rightTree.right);
        boolean ret2=isSymmetricalChild(leftTree.right,rightTree.left);

        return ret1 && ret2;
    }

    public TreeNode mergeTrees(TreeNode rootA,TreeNode rootB){
        if(rootA == null){
            return rootB;
        }
        if(rootB == null){
            return rootA;
        }
        //走到这说明rootA和rootB都不是null
        rootA.val= rootA.val+ rootB.val;
        rootA.left=mergeTrees(rootA.left,rootB.left);
        rootA.right=mergeTrees(rootA.right,rootB.right);

        return rootA;
    }


}
